C++|栈的应用（逆波兰算法）|计算器

后缀式的特点可用于计算表达式的值&＃xff0c;我们通过中缀转后缀的方式可以将原表达式重新排列组合成为计算机易于理解的计算方式。
详情请参考&＃xff1a;逆波兰算法&＃xff08;后缀表达式&＃xff09;

关于中缀转后缀

中缀式转后缀式 如&＃xff1a;
1&＃43;2就是一个中缀式&＃xff0c;转换成后缀式为1 2 &＃43;
1&＃43;2*3…… ……1 2 3 * &＃43;
1&＃43;(2&＃43;5)…… ……1 2 5 &＃43; &＃43;

在计算时&＃xff0c;从最左侧开始先选定一个符号与该符号左边的两个数结合运算。以下&＃xff08;黄色高亮部分&＃xff09;计算过程如下

• 1&＃43;2…… ……1 2 &＃43;

1与2进行&＃43;运算


• 1&＃43;2*3…… ……1 2 3 * &＃43;

1. 最左边的符号 * &＃xff0c;左侧的两个数 2 3计算&＃xff1a;2*3 &＃61; 6表达式&＃xff1a;1 6 &＃43;
2. 最左边的符号 &＃43; &＃xff0c;左侧的两个数 1 6计算&＃xff1a;1&＃43;6 &＃61; 7


• 1&＃43;(2&＃43;5)…… ……1 2 5 &＃43; &＃43;

3. ...计算&＃xff1a;2&＃43;5&＃61;7表达式&＃xff1a;1 7 &＃43;
4. ...计算&＃xff1a;1&＃43;7&＃61;8


如上所示&＃xff0c;使用后缀式可以清晰的表示出表达式中的运算关系&＃xff0c;所有运算符符号中&＃xff0c;优先级最高的在最左边。

计算时从最左侧的符号先开始&＃xff0c;且每个符号都与它左侧最近的两个数据结合。

可以说&＃xff0c;后缀式就是根据计算表达式中的优先级进行设计的。
比如&＃xff0c;在计算表达式中 ’ ( ) ’ 的优先级最高&＃xff0c;因此在转后缀式时遇到 ‘(’ 与 ‘)’ 之间的符号就认为是优先级最高的符号。

eg: a*(b&＃43;c)
a b c &＃43; *过程详解&＃xff1a;
1、&＃61;&＃61;&＃61;a*(b&＃43;c)&＃61;&＃61;&＃61;↑
后缀: a ✔
符号:
2、&＃61;&＃61;&＃61;a*(b&＃43;c)&＃61;&＃61;&＃61;↑
后缀: a
符号: * ✔
3、&＃61;&＃61;&＃61;a*(b&＃43;c)&＃61;&＃61;&＃61;↑
后缀: a
符号: * ( ✔
4、&＃61;&＃61;&＃61;a*(b&＃43;c)&＃61;&＃61;&＃61;↑
后缀: a b ✔
符号: * (
5、&＃61;&＃61;&＃61;a*(b&＃43;c)&＃61;&＃61;&＃61;↑
后缀: a b
符号: * ( &＃43; ✔
6、&＃61;&＃61;&＃61;a*(b&＃43;c)&＃61;&＃61;&＃61;↑
后缀: a b c ✔
符号: * ( &＃43;
7、&＃61;&＃61;&＃61;a*(b&＃43;c)&＃61;&＃61;&＃61;↑
后缀: a b c
符号: * ( &＃43; ) ✔
注&＃xff1a;遇到&＃39;)&＃39;&＃xff0c;后面进来的符号都视为较低优先级符号&＃xff0c;因此把&＃39; ( ) &＃39;内的符号全部转移到后缀式中
8、&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
后缀: a b c &＃43; ✔
符号: *
9、&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
后缀: a b c &＃43; * ✔
符号:


中缀转后缀技巧

中缀转后缀的核心就是&＃xff0c;将优先级高的运算放在最前边计算&＃xff0c;如 … (b&＃43;c)… 形式的表达式 &＃xff0c;要变成 … b c &＃43; … 。后缀式中优先级体现在符号自左向右的顺序&＃xff0c;表达式的关系体现在每个符号与其左边最近的两个数字。

而针对表达式 a&＃43;b-c &＃xff0c;因为 ‘&＃43;’ ‘-’ 优先级相同&＃xff0c;而我们的计算顺序为同优先级自左向右&＃xff0c;则我们认为左边的 ‘&＃43;’ 优先级更高。因此后缀式为 a b &＃43; c - &＃xff0c;其中 a b &＃43; 为(a&＃43;b) 就是原式中优先级高的部分。

而对于 a &＃43; b * c 的表达式&＃xff0c;显然 b*c 的优先级最高&＃xff0c;则后缀式为 a b c * &＃43; 。

在本例中&＃xff0c;函数 void InfixToSuffix(); 进行中缀转后缀计算。

中缀转后缀计算机代码

#include using std::cin;
using std::cout;
using std::endl;template<typename T>
class Stack
{
public:Stack(int _m_size &＃61; 20) :m_size(_m_size), mtop(0){data &＃61; new T[m_size]();}~Stack(){delete[] data;}/* 判空 */bool empty(){return mtop &＃61;&＃61; 0;}void push(int val){if (Full()){throw std::exception("error: Stack is Full !");}data[mtop] &＃61; val;mtop&＃43;&＃43;;}T top(){if (empty()){throw std::exception("error: The stack is empty !");}return data[mtop - 1];}void pop(){if (empty()){throw std::exception("error: Stack is Empty !");}mtop--;}void show(){if (empty()){cout << endl;}else{int i &＃61; 0;while (i < mtop){cout << data[i] << " ";i&＃43;&＃43;;}cout << endl;}}
private:bool Full(){return mtop &＃61;&＃61; m_size;}T* data;int mtop;int m_size;
};/* 计算器类 */
class Calculator
{
public:// 这里m_size 默认给的是40&＃xff0c;m_size限制表达式的长短Calculator(int _m_size &＃61; 40) :m_size(_m_size), m_result(0){m_str &＃61; new char[_m_size &＃43; 1]();}~Calculator(){delete[] m_str;}/* 输入 */void setData(){cin.getline(m_str, m_size - 1); //最多输入m_size -1个&＃xff0c;末尾加&＃39;/0&＃39;}/* 中缀转后缀 */void InfixToSuffix(); /* 把m_str输入的中缀式转换为后缀式 *//* 后缀计算 */void Compure();/* 计算结果 */double Getm_result(){return m_result;}
private:bool IsPop(char a, char b);char* m_str;double m_result;int m_size;};int main()
{while (1) {Calculator ca;ca.setData();ca.InfixToSuffix();ca.Compure();cout << ca.Getm_result() << endl;}return 0;
}// 比较符号优先级&＃xff0c;是否出符号栈
// 栈顶元素b的优先级是否高于符号a&＃xff0c; true/false 出栈b/入栈a
bool Calculator::IsPop(char a, char b) //a为待比较符号&＃xff0c;b为符号栈栈顶元素
{if (b &＃61;&＃61; &＃39;(&＃39;) return false; //‘&＃xff08;’优先级最低 if (a &＃61;&＃61; &＃39;*&＃39; || a &＃61;&＃61; &＃39;/&＃39;){if (b &＃61;&＃61; &＃39;&＃43;&＃39; || b &＃61;&＃61; &＃39;-&＃39;){//可以入符号栈 // 栈外优先级高&＃xff0c;可以继续入栈return false;}else{ return true;}}//if (a &＃61;&＃61; &＃39;&＃43;&＃39; || a &＃61;&＃61; &＃39;-&＃39;)//{//a符号为最低优先级&＃xff0c;符号栈出栈return true;//}
}/* 中缀转后缀 入栈 */
void Calculator::InfixToSuffix()
{// 转换为后缀式后&＃xff0c;为了区分数字&＃xff1a;如5、4……&＃xff0c;在原来的数据增加了分隔符// dst 中存储输入的表达式的后缀式形式 size*2char* dst &＃61; new char[m_size*2](); /* 符号栈 */Stack<char> symbol; // 在转后缀的过程中&＃xff0c;&＃xff08;通过符号优先级&＃xff09;控制符号在后缀式中的位置int i &＃61; 0;int k &＃61; 0;while (m_str[i] !&＃61; &＃39;\0&＃39;){/*----------- 特殊符号判断------------------------------*/if (m_str[i] &＃61;&＃61; &＃39; &＃39;) //如果当前字符是空格&＃xff0c;则往后走一个{i&＃43;&＃43;;continue;}else if (m_str[i] &＃61;&＃61; &＃39;(&＃39;) //左括号直接入栈{symbol.push(m_str[i]);}else if (m_str[i] &＃61;&＃61; &＃39;)&＃39;) //遇到 &＃xff09; &＃xff0c;输出&＃xff08; &＃xff09;之间的所有符号{while (symbol.top() !&＃61; &＃39;(&＃39;){dst[k&＃43;&＃43;] &＃61; symbol.top();dst[k&＃43;&＃43;] &＃61; &＃39; &＃39;;symbol.pop();}symbol.pop();}/*----------------- 数字 -------------------------------*/else if (isdigit(m_str[i])){dst[k&＃43;&＃43;] &＃61; m_str[i];if (!isdigit(m_str[i &＃43; 1])) //数字后加空格{dst[k&＃43;&＃43;] &＃61; &＃39; &＃39;;}}/*----------------- 运算符 -------------------------------*/else{switch (m_str[i]){case &＃39;&＃43;&＃39;:case &＃39;-&＃39;:case &＃39;*&＃39;:case &＃39;/&＃39;:if (symbol.empty()) //如果符号栈为空&＃xff0c;直接入符号{symbol.push(m_str[i]);}else //否则&＃xff0c;判断是否选择入符号栈还是出栈顶元素{// 栈内符号优先级高于栈外&＃xff0c;出栈。 IsPop &＃61;&＃61; true;if (IsPop(m_str[i], symbol.top())) //出符号栈{dst[k&＃43;&＃43;] &＃61; symbol.top();symbol.pop();continue;}else //当前符号优先级高&＃xff0c;入符号栈{symbol.push(m_str[i]);}}break;default:break;}}i&＃43;&＃43;; /* 遍历下一字符 */}/*字符串已遍历完&＃xff0c;把符号栈中剩余的符号入栈到数字栈中 */while (!symbol.empty()){dst[k&＃43;&＃43;] &＃61; symbol.top();symbol.pop();}dst[k] &＃61; &＃39;\0&＃39;;// 输出后缀式//cout <// 后缀表达式 保存到 Calculator::m_str中// 交换dst 与 m_str 的堆区空间char* tmp &＃61; dst;dst &＃61; m_str;m_str &＃61; tmp; delete[]dst;
}void Calculator::Compure()
{/* 辅助栈 */Stack<double> st;int i &＃61; 0;while (m_str[i] !&＃61; &＃39;\0&＃39;){/*----------- 特殊符号判断------------------------------*/if (m_str[i] &＃61;&＃61; &＃39; &＃39;) //如果当前字符是空格&＃xff0c;则往后走一个{i&＃43;&＃43;;continue;}/*----------------- 数字 -------------------------------*/else if (isdigit(m_str[i])){double tmp &＃61; 0;while (m_str[i] !&＃61; &＃39; &＃39;){tmp &＃61; tmp * 10 &＃43; m_str[i] - &＃39;0&＃39;;i&＃43;&＃43;;}st.push(tmp);}/*----------------- 运算符 -------------------------------*/else if (!st.empty()) //非空{double tmp &＃61; 0;switch (m_str[i]){case &＃39;&＃43;&＃39;:tmp &＃43;&＃61; st.top();st.pop();tmp &＃43;&＃61; st.top();st.pop();st.push(tmp);break;case &＃39;-&＃39;:tmp -&＃61; st.top();st.pop();tmp &＃43;&＃61; st.top();st.pop();st.push(tmp);break;case &＃39;*&＃39;:tmp &＃61; st.top();st.pop();tmp *&＃61; st.top();st.pop();st.push(tmp);break;case &＃39;/&＃39;:{tmp &＃61; st.top();st.pop();if (tmp !&＃61; 0){tmp &＃61; st.top() / tmp;st.pop();st.push(tmp);}else{throw std::exception("error: Divisor of 0 &＃xff01;");}}break;default:break;}}i&＃43;&＃43;; /* 遍历下一字符 */}this->m_result &＃61; st.top();st.top();
}

运行截图&＃xff1a;

注&＃xff1a;在计算器类中

Calculator(int _m_size &＃61; 40) :m_size(_m_size), m_result(0)
{}


构造函数 _m_size 默认设置的为40&＃xff0c;这将影响到我们输入的计算表达式的长度&＃xff0c;我们在编译时可以根据需求自行更改代码。